package com.mlh.sort;

import java.util.Arrays;

//桶排序（左神）
public class BucketSort {
	public static void main(String[] args) {
		int[] arr = {53, 17, 78, 9, 45, 65, 87, 32, 345, 7, 67, 1, 1, 1, 1, 1, 1, 1, 45, 6, 7, 8, 5, 3, 234, 4, 5, 67, 7, 8, 9, 2147483647, -1, -4, -77, -56969690, -6666, -2147483648};
		method2(arr);
		System.out.println(Arrays.toString(arr));
	}

	//该方法只能处理0和正整数数组
	public static void method1(int[] arr) {
		int n = arr.length;
		if (n <= 1) {
			return;
		}
		int digit = method1FindMaxDigit(arr);
		int[] axuiliary = new int[n];
		for (int i = 1; i <= digit; i++) {
			int modNum = (int) Math.pow(10, i);//计算数位
			int[] count = new int[10];
			//计算count数组
			for (int j = 0; j < arr.length; j++) {
				int temp = arr[j] % modNum / (modNum / 10);//计算第digit位上的数字
				count[temp]++;
			}
			//计算count'数组
			for (int j = 1; j < 10; j++) {
				count[j] = count[j - 1] + count[j];
			}
			//从右往左开始扫描数组
			for (int j = n - 1; j >= 0; j--) {
				int temp = arr[j] % modNum / (modNum / 10);
				axuiliary[count[temp] - 1] = arr[j];
				count[temp]--;
			}
			//copy回原数组
			for (int j = 0; j < n; j++) {
				arr[j] = axuiliary[j];
			}
		}
	}

	public static int method1FindMaxDigit(int[] arr) {
		int max = Integer.MIN_VALUE;
		int digit = 0;
		for (int i = 0; i < arr.length; i++) {
			max = arr[i] > max ? arr[i] : max;
		}
		if (max == 0) {
			return 1;
		}
		while (max != 0) {
			max /= 10;
			digit++;
		}
		return digit;
	}

	//该方法可以处理负数和正数数组
	public static void method2(int[] arr) {
		//利用双指针将负数放到数组前面，正数放到数组后面
		int n = arr.length;
		int left = 0, right = n - 1;
		while (left <= right) {
			if (arr[left] >= 0) {
				int temp = arr[left];
				arr[left] = arr[right];
				arr[right] = temp;
				right--;
			} else {
				left++;
			}
		}
		//对正负数组分别处理
		int[] negArr = new int[left];
		int[] posArr = new int[arr.length - right - 1];
		int minCount = 0;//记录Integer.MIN_VALUE的元素数量
		//把负数变成正数数组，最关键的是把Integer.MIN_VALUE+1，这样才能表示成正数，不就溢出
		for (int i = 0; i < left; i++) {
			if (arr[i] == Integer.MIN_VALUE) {
				arr[i] += 1;//这里将其+1 就可以用整数表示
				minCount++;
			}
			negArr[i] = -arr[i];
		}
		for (int i = right + 1; i < arr.length; i++) {
			posArr[i - right - 1] = arr[i];
		}
		//处理好了 直接用正数的来处理即可
		method1(negArr);
		method1(posArr);
		//将两个处理好的数组恢复到原数组，负数数组需要逆序打印且乘以-1
		for (int i = 0; i < negArr.length; i++) {
			arr[i] = -negArr[negArr.length - 1 - i];
		}
		for (int i = negArr.length; i < arr.length; i++) {
			arr[i] = posArr[i - negArr.length];
		}
		//最后处理一下负数
		for (int i = 0; i < minCount; i++) {
			arr[i] -= 1;//最后将这些负数减回来
		}
	}
}
